package cn.fansunion.leecode.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字符串中的第一个唯一字符
 * 给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
 * https://leetcode-cn.com/problems/first-unique-character-in-a-string/
 * @author wen.lei@brgroup.com
 *
 * 2022-2-16
 */
public class FirstUniqueCharacter {
    
    //输入: s = "loveleetcode"
        //输出: 2
    /**
     * 遍历字符串，统计字符串中每个字符的数量charCountMap;再遍历一次，寻找第一个只存在一次的字符串
     * 方法2：用集合List维护只存在一次的字符，只用遍历一次，判断会多一些
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        Map<Character, Integer> charCountMap =charCountMap(s);
        for(int index=0;index<s.length();index++) {
            char ch=s.charAt(index);
            if(charCountMap.get(ch)==1) {
                return index;
            }
        }
        return -1;
    }
    
    
    /**
     * 遍历数组，每个数字和对应的次数map
     * @param arr
     * @return
     */
    private Map<Character, Integer> charCountMap(String s) {
        Map<Character, Integer> charCountMap = new HashMap<>();
        char[] arr=s.toCharArray();
        for (Character num : arr) {
            Integer count=charCountMap.get(num);
            if(count==null) {
                count=1;
            }else{
                count++;
            }
            charCountMap.put(num, count);
        }
        return charCountMap;
    }
    
    /**
     * 维护2个集合：只出现一次的onlyOneCharList和曾经出现多次的charRepeatList。<br/>
     * 遍历一次，从onlyOneCharList取第1个字符对应的索引。没有，-1
     * @param s
     * @return
     */
    public int firstUniqCharList(String s) {
        List<Character> onlyOneCharList= new ArrayList<Character>();
        List<Character> charRepeatList= new ArrayList<Character>();
        for(int index=0;index<s.length();index++) {
            char ch=s.charAt(index);
            //疑似第一次出现
            if(!onlyOneCharList.contains(ch)) {
                //真正的第一次出现
                if(!charRepeatList.contains(ch)) {
                    onlyOneCharList.add(ch);
                }
            }else {
                //出现多次
                onlyOneCharList.remove((Character)ch);
                charRepeatList.add(ch);
            }
        }
        if(onlyOneCharList.size()>=1) {
            char onlyCharFirst=onlyOneCharList.get(0);
            return s.indexOf(onlyCharFirst);
        }
        return -1;
    }
   
}
